package lcr;

import java.util.*;

public class Test0109 {
    public static void main(String[] args) {
        Solution0109_1 solution = new Solution0109_1();
        String[] deadends = {"0201","0101","0102","1212","2002"};
        String target = "0202";
        System.out.println(solution.openLock(deadends, target));
    }
}

class Solution0109_1 {
    public int openLock(String[] deadends, String target) {
        Set<String> deadendsSet = new HashSet<>(Arrays.asList(deadends));
        if (deadendsSet.contains("0000")) return -1;
        Deque<String> queue = new ArrayDeque<>();
        queue.addLast("0000");

        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String poll = queue.poll();
                if (poll.equals(target)) return count;
                getNext(poll, deadendsSet, queue);
            }
            count++;
        }

        return -1;
    }

    public void getNext(String s, Set<String> records, Deque<String> queue) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            char pre = c=='0'?'9':(char)(c-1);
            char next = c=='9'?'0':(char)(c+1);

            chars[i] = pre;
            String preString = String.valueOf(chars);
            if (!records.contains(preString)) {
                queue.addLast(preString);
                records.add(preString);
            }
            chars[i] = next;
            String nextString = String.valueOf(chars);
            if (!records.contains(nextString)) {
                queue.addLast(nextString);
                records.add(nextString);
            }
            chars[i] = c;
        }
    }
}